package com.java.util;

import com.java.util.pojo.RequestContent;
import com.java.util.pojo.User;
import org.apache.commons.collections4.CollectionUtils;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 回溯法解决单个集合组合问题。
 */
public class BackSearch {


    /**
     * 这个是Map-Map
     *
     * @param args
     */
    public static void main(String[] args) {
        List<RequestContent> list = new ArrayList<>();

        list.add(new RequestContent(1, "aa-1", "h111", 1, false));
//        list.add(new User(2, "bb-1", "h111", 1, false));
        list.add(new RequestContent(3, "aa-2", "h111", 1, false));
        list.add(new RequestContent(2, "aa-2", "h111", 2, false));

        list.add(new RequestContent(5, "aa-2", "h222", 3, false));
        list.add(new RequestContent(5, "aa-2", "h222", 2, false));
        list.add(new RequestContent(5, "aa-2", "h222", 1, false));

        list.add(new RequestContent(4, "bb-2", "h333", 2, false));
        list.add(new RequestContent(4, "bb-2", "h333", 1, false));
        list.add(new RequestContent(4, "bb-2", "h333", 3, false));
//        list.add(new RequestContent(5, "cc-2", "h222", 0, false));
//        list.add(new User(6, "bb-2", "h222", 2, false));

//        list.add(new RequestContent(7, "cc-1", "h333", 0, false));
//        list.add(new RequestContent(7, "cc-1", "h444", 0, false));
//        list.add(new RequestContent(7, "cc-1", "h555", 0, false));
//        list.add(new User(8, "cc-1", "h444", 0, false));


        List<List<RequestContent>> combinations = new ArrayList<>();
        backtrack1(list, 0, new ArrayList<>(), 3, combinations);

        // 打印所有找到的组合（但在这个例子中，我们实际上在找到目标组合后就停止了）
        for (List<RequestContent> combo : combinations) {

            combo.stream().forEach(System.out::println);
        }

        Boolean valid = valid(list, 3);
        System.out.println(">>>>>>>>>>>>>>> 结果为 " + valid);
    }


    private static Boolean valid(List<RequestContent> list, int requiredCount) {

        Map<String, List<Integer>> map = new HashMap<>();
        int i = 0;
        while (i < list.size()) {
            Boolean valid = beValid(map, requiredCount);

            if (!valid) {
                RequestContent o = list.get(i);
                List<Integer> pinSet = map.getOrDefault(o.getPreviewContent(), new ArrayList<>());
                pinSet.add(o.getPinMode());
                map.put(o.getPreviewContent(), pinSet);
                i++;
            } else {
                return true;
            }
        }
        return beValid(map, requiredCount);
    }

    private static Boolean beValid(Map<String, List<Integer>> map, int requiredCount) {
        if (map.size() < requiredCount) {
            return Boolean.FALSE;
        }

        Iterator<Map.Entry<String, List<Integer>>> iterator = map.entrySet().iterator();

        int zeroCount = 0;
        List<Integer> set = new ArrayList<>();
        while (iterator.hasNext()) {
            Map.Entry<String, List<Integer>> entry = iterator.next();

            List<Integer> values = entry.getValue();

            long count = values.stream().filter(i -> i == 0).count();
            zeroCount += count;

            values.stream().filter(i -> i != 0)
                    .max(Integer::compareTo)
                    .ifPresent(set::add);
        }

        int sum = set.stream().mapToInt(e -> e).sum();
        int rqSum = 6;

        if (zeroCount > requiredCount || sum >= rqSum) {
            return Boolean.TRUE;
        }

        int diff = requiredCount - set.size();
        if (zeroCount >= diff) {
            return Boolean.TRUE;
        }

        return Boolean.FALSE;
    }

    private static void backtrack(List<User> users, int start, List<User> current, int k, List<List<User>> result) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < users.size(); i++) {
            current.add(users.get(i));
            backtrack(users, i + 1, current, k, result); // 注意这里从i+1开始，避免重复选择同一个元素
            current.remove(current.size() - 1);
        }
    }


    private static void findCombinations(List<String> nums, int start, List<String> current, int k, List<String> target, List<List<String>> result) {
        if (current.size() == k) {
            // 检查当前组合是否等于目标组合
            if (current.equals(target)) {
                // 如果找到了目标组合，可以打印它或进行其他操作，然后返回以终止进一步搜索
//                System.out.println("Found target combination: " + current);
                result.add(new ArrayList<>(current));

                // 注意：在这个例子中，我们不再将组合添加到结果列表中，因为我们只想找到并终止
                // 如果你仍然想保留所有组合，包括目标组合，请取消下面的 return 语句
                return; // 终止进一步搜索
            }
            // 如果不是目标组合但你想保留所有组合，则取消注释下一行
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < nums.size(); i++) {
            current.add(nums.get(i));
            findCombinations(nums, i + 1, current, k, target, result); // 注意这里从 i+1 开始以避免重复
            if (!current.equals(target)) {
                current.remove(current.size() - 1); // 回溯
            }
        }
    }



    private static void findCombinations1(List<String> nums, int start, List<String> current, int k, List<String> target, List<List<String>> result) {
        if (current.size() == k) {
            if (current.equals(target)) {
                // 如果找到了目标组合，可以打印它或进行其他操作，然后返回以终止进一步搜索
                System.out.println("Found target combination: " + current);
                result.add(new ArrayList<>(current));

                // 注意：在这个例子中，我们不再将组合添加到结果列表中，因为我们只想找到并终止
                // 如果你仍然想保留所有组合，包括目标组合，请取消下面的 return 语句
                return; // 终止进一步搜索
            }
            // 如果不是目标组合但你想保留所有组合，则取消注释下一行
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < nums.size(); i++) {
            current.add(nums.get(i));
            findCombinations(nums, i + 1, current, k, target, result); // 注意这里从 i+1 开始以避免重复
            if (!current.equals(target)) {
                current.remove(current.size() - 1); // 回溯
            }
        }
    }


    private static void backtrack1(List<RequestContent> users, int start, List<RequestContent> current,final int k, List<List<RequestContent>> result) {
        if (current.size() == k) {
            if (idGood(current, k)) {

                // 注意：在这个例子中，我们不再将组合添加到结果列表中，因为我们只想找到并终止
                // 如果你仍然想保留所有组合，包括目标组合，请取消下面的 return 语句
//                System.out.println("Found target combination: " + current);
                result.add(new ArrayList<>(current));
                return;
            }
            // 如果不是目标组合但你想保留所有组合，则取消注释下一行
//            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < users.size(); i++) {
            current.add(users.get(i));
            backtrack1(users, i + 1, current, k, result); // 注意这里从i+1开始，避免重复选择同一个元素
            if (!idGood(current, k)) {
                current.remove(current.size() - 1); // 回溯
            }
        }
    }


    private static Boolean idGood(List<RequestContent> adDetailList, final int requiredCount) {
        if (CollectionUtils.isEmpty(adDetailList) || adDetailList.size() < requiredCount) {
            return Boolean.FALSE;
        }
        // 进来的是组合的3 个详情，判断是不是符合条件，去重content，判断pin是否够用
        Map<String, List<RequestContent>> tempMap = adDetailList.stream().collect(Collectors.groupingBy(RequestContent::getPreviewContent));

        // 去重之后数量小于给定的值，也不用比较pin了
        if (tempMap.size() < requiredCount) {
            return Boolean.FALSE;
        }

        // 校验pin position
        // 如果Any的个数加上其他pin1/pin2/pin3的个数等于要求的个数就认为是对的。
        Map<Integer, Long> collect = adDetailList.stream().collect(Collectors.groupingBy(RequestContent::getPinMode, Collectors.counting()));

        Long anyCount = collect.getOrDefault(0, 0L);
        long pinCount = collect.keySet().stream().filter(i -> 0 != i).count();

        if ((anyCount + pinCount) == requiredCount) {
            return Boolean.TRUE;
        }

        return Boolean.FALSE;
    }
}
